package quantum.algorithms;

import org.apache.commons.math.complex.Complex;

import quantum.state.QuantumState;
import quantum.utils.Utils;

public class Shor {
	public Shor() {
	}
	
	public int execute(int n) {
		while( true ) {
			int a = (int) (Math.random() * n);
			if( Utils.gcd(a, n) != 1 ) 
				return a;
			
			int r = findPeriod(a, n);
			if( r % 2 != 0 ) {
				continue;
			}
			int rt = Utils.powmod(a, r, n);
			rt = (int) Math.sqrt(rt);
			if( rt % n != n-1 ) {
				int candidate1 = Utils.gcd(rt + 1, n);
				if( candidate1 == 1 || n % candidate1 != 0 ) {
					return Utils.gcd(rt - 1, n);
				} else {
					return candidate1;
				}
			}
		}
	}
	
	private int findPeriod(int a, int n) {
		int answer = 0;
		int q = (int) Math.floor(Math.log(n*n) / Math.log(2));
		int Q = 1 << q;
		QuantumState input = new QuantumState(q);
		QuantumState output = new QuantumState(q);
		double init_amp = 1.0 / Math.sqrt(Q);
		boolean done = false;
		
		while( !done ) {
			// Initialize input and output registers
			// Initialize input with amplitudes 1 / sqrt(Q)
			for(int i = 0 ; i < Q ; i++) {
				input.setAmplitude(i, new Complex(init_amp, 0));
				int pm = Utils.powmod(a, i, n);
				Complex amp = output.getAmplitude(pm);
				output.setAmplitude(pm, amp.add(Complex.ONE));
			}
			output.normalize();
			
			// Measure state of output register
			int observed_state = output.measure();
			// Simulates the effects on input register of collapsing the output register 
			for(int i = 0 ; i < input.numAmplitudes() ; i++) {
				if( Utils.powmod(a, i, n) == observed_state ) {
					input.setAmplitude(i, Complex.ONE);
				} else {
					input.setAmplitude(i,  Complex.ZERO);
				}
			}
			input.normalize();
			
			// Apply the Quantum Fourier Transform on the input register
			input = Utils.applyFourierTransform(input);
			int y = input.measure();
			
			double inverse_period_multiple = ((double)y) / Q;
			int candidate_period = Utils.bestDenominator(inverse_period_multiple, n);
			int counter = 0;
			// check if 'candidate_period' is indeed a period of the powmod function and adjust it if not by 
			// using multiples of 'candidate_period' until 3*candidate_period
			while( counter < 3 ) {
				if( Utils.powmod(a, 0, n) != Utils.powmod(answer, candidate_period, n) ) {
					candidate_period += candidate_period;
				} else {
					done = true;
					break;
				}
			}
		}
		
		return answer;
	}
}
